import java.util.ArrayList;
import java.util.List;

public class SpiralMatrix {
    public List<Integer> spiralOrder(int matrix[][]) {
        int m = matrix.length;
        int n = matrix[0].length;

        List<Integer> res = new ArrayList<>();
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        int curX = 0, curY = 0;
        while (res.size() < m * n) {
            while (curY <= right) {
                res.add(matrix[curX][curY]);
                curY++;
            }
            curY--;
            curX++;
            if (++top > bottom) break;

            while (curX <= bottom) {
                res.add(matrix[curX][curY]);
                curX++;
            }
            if (--right < left) break;
            curX--;
            curY--;
            while (curY >= left) {
                res.add(matrix[curX][curY]);
                curY--;
            }
            if (--bottom < top) break;
            curY++;
            curX--;
            while (curX >= top) {
                res.add(matrix[curX][curY]);
                curX--;
            }
            if (++left > right) break;
            curX++;
            curY++;
        }
        return res;
    }
}
